#leetcode题目34：在排序数组中查找元素的第一个和最后一个位置
#难度：中等
#时间复杂度：O(logn)
#空间复杂度：O(1)
#方法：二分查找

#策略：题目中暗示时间复杂度为O(logn)，所以使用二分查找

#来源于第二个视频合集

from typing import List
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return [-1,-1]
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)//2
            if target>nums[mid]:
                left=mid+1

            elif target<nums[mid]:
                right=mid-1
            else:
                x,y=mid,mid
                while x>0 and nums[x-1]==target:
                    x-=1
                while y<len(nums)-1 and nums[y+1]==target:
                    y+=1
                return [x,y]


        return [-1,-1]

#测试数据
nums=[5,7,7,8,8,10]
target=8
#预期输出：[3,4]
solution=Solution()
print(solution.searchRange(nums,target))

nums=[5,7,7,8,8,10]
target=6
#预期输出：[-1,-1]          
solution=Solution()
print(solution.searchRange(nums,target))

